package sword.T19;

/**
 * @File Info: leetcode -- <Solution>
 * @Author: 18362
 * @Create: 2022-03-27 13:52:31 星期日
 */

class Solution {
    public boolean isMatch(String s, String p) {
        char[] pattern = getPattern(p);
        boolean[] dp = new boolean[s.length()+1];
        dp[0] = true;
        for (int i=0; i<pattern.length; ++i) {
            // pattern[i], s.charAt(j-1)
            boolean last = dp[0];
            dp[0] = (dp[0] && match(pattern[i], '0', false));
            for (int j=1; j<=s.length(); ++j) {
                boolean temp = dp[j];
                if (last && match(pattern[i], s.charAt(j-1), false))
                    dp[j] = true;
                else if (temp && match(pattern[i], '0', false))
                    dp[j] = true;
                else if (dp[j-1] && match(pattern[i], s.charAt(j-1), true))
                    dp[j] = true;
                else
                    dp[j] = false;
                last = temp;
            }
        }
        return dp[s.length()];
    }

    private boolean match(char pattern, char target, boolean more) {
        if (more) {
            if ((pattern >= 'a' && pattern <= 'z') || pattern == '.')
                return false;
            if (pattern == '-')
                return true;
            return (char) (pattern-'A'+'a') == target;
        }
        if (target == '0') {
            if ((pattern >= 'a' && pattern <= 'z') || pattern == '.')
                return false;
            return true;
        }
        if (pattern == '-' || pattern == '.')
            return true;
        if (pattern >= 'A' && pattern <= 'Z') {
            return (char) (pattern-'A'+'a') == target;
        } else {
            return pattern == target;
        }
    }

    private char[] getPattern(String p) {
        int n = p.length();
        for (int i=0; i<p.length(); ++i) {
            if (p.charAt(i) == '*')
                n--;
        }
        char[] pattern = new char[n];
        int j = n - 1, i = p.length()-1;
        while (j >= 0) {
            if (p.charAt(i) == '*') {
                if (p.charAt(i-1) == '.')
                    pattern[j] = '-';
                else
                    pattern[j] = (char) (p.charAt(i-1) - 'a' + 'A');
                i-=2;
            } else {
                pattern[j] = p.charAt(i);
                i--;
            }
            j--;
        }
        return pattern;
    }
}